<html>

<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> 
  <link rel="stylesheet" title="Default" href="http://acm.math.spbu.ru/~sk1/colorer/my.css">

  <script src="http://acm.math.spbu.ru/~sk1/colorer/highlight.js"></script>
  <script src="http://acm.math.spbu.ru/~sk1/colorer/cpp.js"></script>
  <script>hljs.initHighlightingOnLoad();</script>
</head>

<body>

<pre><code>
/**
 * Author: Sergey Kopeliovich (Burunduk30@gmail.com5
 * Date: 2013.10.18
 */

#include &lt;cstdio&gt;
#include &lt;cstring&gt;
#include &lt;cassert&gt;
#include &lt;algorithm&gt;
#include &lt;vector&gt;

using namespace std;

#define forn(i, n) for (int i = 0; i &lt; (int)(n); i++)
#define pb push_back

const int V = 26 * 26;
const int L = 1000;
const double eps = 1e-6;
const double inf = 1e20;

int n;
char s[L + 1];
vector &lt;int&gt; c[V], w[V];
double d[V];

int get( char *s )
{
  return (s[0] - 'a') * 26 + (s[1] - 'a');
}

void addE( int a, int b, int l )
{
  c[a].pb(b), w[a].pb(l);
}

bool solve( double W )
{
  forn(i, V)
    d[i] = 0;
  forn(_, V + 1)
  {
    int run = 0;
    forn(v, V)
      forn(i, c[v].size())
      {
        int x = c[v][i];
        double t = W - w[v][i];
        if (d[x] &gt; d[v] + t + eps)
        {
          d[x] = max(d[v] + t, -inf), run = 1;
          if (_ == V)
            return 1;
        }
      }
    if (!run)
      return 0;
  }
  return 0;
}

int main()
{
  while (scanf("%d ", &n) == 1 && n)
  {
    forn(i, V)
      c[i].clear(), w[i].clear();
    forn(i, n)
    {
      gets(s);
      int l = strlen(s);
      addE(get(s + 0), get(s + l - 2), l);
    }

    double l = -1, r = L, m;
    forn(k, 20)
      if (solve(m = (l + r) / 2))
        l = m;
      else
        r = m;
    if (l &lt; 0)
      puts("No solution.");
    else
      printf("%.2f\n", l);
  }
  return 0;
}

</code></pre>

</body>
</html>

<font style="visibility:hidden">
